package p.a2.a;
/*
 * @author: Stefan Schasse 569372
 */

/*****************************************************
 *
 * Optimierung nach http://www.markdiamond.com.au/download/joous-3-1-1.pdf
 * Ziffer 0 in Zahl: Produkt ist 0
 * Ziffer 1 in Zahl: Es gibt ein kleinere Zahl mit gleichem Produkt
 * http://oeis.org/A003001: solutions: The smallest numbers having multiplicative persistences of 1, 2, ... are 10, 25, 39, 77, 679, 6788, 68889, 2677889, 26888999, 3778888999, 277777788888899
 *
 *
 ***************************************************/


public class Quer {

	public static int qp(long zahl) {
		int grad=0;
		long produkt=0;
		do {    // schleife zum k(x) berechnen
			produkt=1;       // produkt initialisieren
			grad++;           // grad hochzählen
			while(zahl!=0){    // solange die zahl noch nicht verarbeitet wurde
				produkt*=zahl%10;  //   produkt mit letzter ziffer mutliplizieren (modulo10 rest
				zahl/=10;         // letzte ziffer streichen (durch 10 teilen integer)
			}
			zahl=produkt;
		} while (produkt>=10); // schleife solange bis das Querrodukt einstellig ist
		// System.out.println(":x produkt:"+produkt+" g:"+grad);
		return grad;
	}



	public static boolean shortcut(long zahl) {
		boolean answer=false;
		int z=0;
		while(zahl!=0){
			// System.out.print(zahl+": ");
			z=(int) zahl%10;
			if ((z==1) | (z==0)) {  // abbruch wenn eine stelle eine 0 oder 1 enthält (s.o.)
				answer=true; // abbruch mARKIEREN
				break;
			}
			zahl=zahl/=10;  // stelle wegstreichen
		}
/*
		String s="";
		s=""+zahl;
		if ((s.contains("0")) | (s.contains("1"))) answer=true;
*/		
		
		
		return answer;
	}

	public static void main(String[] args) {
		int Kmax = Integer.parseInt(args[0]);  // argumentenübername
		long x=0; // init zahl
		int mp=0;
		int punkt=0;
		long startZeit = System.currentTimeMillis(); //stopuhr
		// System.out.println("Start:"+startZeit);
		for (int k=1 ; k<=Kmax; k++) {   // schleife k durchzaehlen bis kmax
			do {
				x++;	// zahl hochzählen
				if (shortcut(x)==false) {	// notwendigkeit der berechnung prüfen
					mp=qp(x);		// querprodukt berechnen
				} else {
					mp=0; //qp(x);		// oder halt auch nicht
				}
				//System.out.println(x);
			} while (mp<k);
			System.out.println(k+" Schritte: "+x+" Zeit:"+((System.currentTimeMillis()-startZeit)));
		}

	}
}